/*
 * egg_carton.c
 *
 *  Created on: Oct 1, 2012
 *      Author: fredrik
 */


#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

//Parameters for the problem.
#define T_MAX 100
#define D_T 1
#define F_TARGET 20
#define N_NEIGHBORS 5 //The number of neighbors to be generated each itereation

//Problem specific defines go here
#define N_ROWS 6
#define N_COLS 6
#define N_EGGS_IN_LINE 2


typedef struct{
	//Fill in attributes about state for the specific problem

	//Two-dimensional array with a 1 if there is an egg
	//at a given spot and a 0 if not
	int carton[N_ROWS][N_COLS];

	int n_eggs;

}state_t;

state_t gen_init_state(void){
	int i,j;
	state_t init_state;

	for(i = 0; i < N_ROWS; i++){
		for(j = 0; j < N_COLS; j++){
			init_state.carton[i][j] = 0;
		}
	}
	init_state.n_eggs = 0;



	return init_state;
}



double obj_func(state_t state){
	//Fill inn the objective function for the specific problem
	double ret_val = 0;
	int total_eggs = 0;
	int i,j;

	//Give one point for each egg in carton
	for(i = 0; i < N_ROWS; i++){
		for(j = 0; j < N_COLS; j++){
			total_eggs += state.carton[i][j];
		}
	}

	int collisions = 0;

	//Count collisions in rows
	for(i = 0; i < N_ROWS; i++){
		int row_eggs = 0;
		for(j = 0; j < N_COLS; j++){
			row_eggs += state.carton[i][j];
		}
		collisions += (row_eggs > N_EGGS_IN_LINE ? row_eggs - N_EGGS_IN_LINE : 0);
	}

	//Count collisions in columns
	for(i = 0; i < N_COLS; i++){
		int col_eggs = 0;
		for(j = 0; j < N_ROWS; j++){
			col_eggs += state.carton[j][i];
		}
		collisions += (col_eggs > N_EGGS_IN_LINE ? col_eggs - N_EGGS_IN_LINE : 0);
	}

	//Count collisions in diagonals
	//The diagonal traversal is inspired by: http://stackoverflow.com/questions/1779199/traverse-matrix-in-diagonal-strips

	int slice;
	//Starts in the top left and checks diagonals down to the left
	for (slice = 0; slice < N_ROWS+N_COLS-1; slice++){
		int j;
		int slice_eggs = 0;
		int slice_start = slice < N_COLS ? 0 : slice - N_COLS + 1;
		int slice_end = slice < N_ROWS ? slice : N_ROWS - 1;
		for(j = slice_start; j <= slice_end; j++){
			slice_eggs += state.carton[j][slice - j];
		}
		collisions += (slice_eggs > N_EGGS_IN_LINE ? slice_eggs - N_EGGS_IN_LINE : 0);
	}

	//Starts in the bottom left and checks diagonals up to the left
	for (slice = 0; slice < N_ROWS+N_COLS-1 ; slice++){
		int j;
		int i = slice < N_COLS ? 0 : slice - (N_COLS - 1);
		int slice_eggs = 0;
		int slice_start = slice < N_COLS ? N_ROWS - 1 : (N_ROWS + N_COLS - 1 - slice - 1) ;
		int slice_end = slice < N_ROWS ? N_ROWS - slice - 1 : 0;
		for(j = slice_start; j >= slice_end; j--){
			slice_eggs += state.carton[j][slice - j];
			i++;
		}
		collisions += (slice_eggs > N_EGGS_IN_LINE ? slice_eggs - N_EGGS_IN_LINE : 0);
	}

	//You get one point for every egg in the carton and lose three points for every egg over the limit i a line

	ret_val = total_eggs - 3*collisions;

	return ret_val;
}

void generate_neighbors(state_t state, state_t* neighbor_array){
	int i,random_row,random_col;

	//We always keep the current state in case all the others are worse
	neighbor_array[0] = state;

	for(i = 1; i < N_NEIGHBORS; i ++){
		neighbor_array[i] = state;
		random_row = rand() % N_ROWS;
		random_col = rand() % N_COLS;
		if(
		neighbor_array[i].carton[random_row][random_col] = 1;
		neighbor_array[i].n_eggs++;
	}
}

void print_state(state_t state){
	int i,j;

	printf("Eggs placed: %d\n", state.n_eggs);

	for(i = 0; i < N_ROWS; i++){
		for(j = 0; j < N_COLS; j++){
			printf(" _");
		}
		printf("\n");
		for(j = 0; j < N_COLS; j++){
			printf("|%c",state.carton[i][j]?'*':' ');
		}
		printf("|\n");
	}
	for(j = 0; j < N_COLS; j++){
		printf(" _");
	}

}

int main(int argc, char** argv){
	int i;
	int n_iterations = 0;
	srand(time(NULL));
	//The current sate
	state_t state = gen_init_state();
	//Array holding the neighbors of current state
	state_t neighbors[N_NEIGHBORS];
	double neighbors_obj_val[N_NEIGHBORS];
	state_t best_neighbor;
	double best_neighbor_val;
	//Variable that represents how close we are to the goal
	double q;
	//Probability of doing exploring instead of exploiting
	double p;
	//A random number generated to decide between exploring and exploiting
	double x;
	//The temperature or "jitter"
	double temp = T_MAX;
	//Current states objective value;
	double obj_value = obj_func(state);
	while(1){
		printf("Iteration number: %d, objective value: %f\n", n_iterations, obj_value);

		//Check if we have reached the goal
		if(obj_value >= F_TARGET || n_iterations > 1000){
			break;
		}

		generate_neighbors(state, neighbors);

		//Find the best neighbor
		best_neighbor_val = 0;
		for(i = 0; i < N_NEIGHBORS; i++){
			neighbors_obj_val[i] = obj_func(neighbors[i]);
			if(neighbors_obj_val[i] > best_neighbor_val){
				best_neighbor = neighbors[i];
				best_neighbor_val = neighbors_obj_val[i];
			}
		}
		//Calculate q HER ER DET ET PROBLEM!! HVA GJØR VI NÅR obj_value er 0????
		if(obj_value == 0){
			DEL PÅ 1 i stedet for null....
		}
		else{
			q = (best_neighbor_val - obj_value)/obj_value;
		}

		//Calculate p
		p = exp(-q/temp);
		if(p > 1){
			p = 1;
		}

		//Make a random number between 0 and 1
		x = (double)rand()/RAND_MAX;

		//Decide between exploitation and exploration
		if(x > p){
			state = best_neighbor;
		}
		else{
			state = neighbors[rand() % N_NEIGHBORS];
		}
		obj_value = obj_func(state);

		//Decrease temperature
		temp -= D_T;

		n_iterations++;


	}

	//Print the solution

	printf("Solution found after %d iterations\n", n_iterations);
	print_state(state);

	return 0;
}





